Qué son los Árboles en gestión de datos

Un árbol es una colección no vacía de nodos y aristas que cumplen ciertos requisitos. Se utiliza principalmente para representar jerarquía y ser utilizado en todo lo que conlleva establecer un orden en un conjunto de valores.

Formalización

Forma no recursiva

Se distingue un nodo como raíz. A cada nodo b, exceptuando la raíz, le llega una arista desde exactamente un nodo a, el cual se le llama padre de b. Decimos que b es uno de los hijos de a. Hay un único camino desde la raíz hasta cada nodo.

Forma recursiva

Un árbol T es un conjunto finito, no vacío de nodos T = {r} ∪ T1 ∪ T2 ∪ L ∪ Tn con las siguientes propiedades:

Un nodo del conjunto es designado como raíz del árbol (r).
Los nodos restantes son particionados en N ≥ 0 subconjuntos, T1 , T2 , K , Tn en el que cada uno es un árbol.

Definiciones

Los nodos que no tienen hijos reciben el nombre de hojas o nodos terminales.
Frecuentemente las hojas son nodos diferentes a los que no son hojas, por ejemplo, pueden no tener nombre o información asociada. Entonces en tales situaciones se denomina nodos externos a las hojas y nodos internos a los nodos que no son hojas.
El grado de un nodo es el número de subárboles asociados a ese nodo.
La profundidad o nivel de un nodo en un árbol es la longitud del camino que va desde la raíz hasta ese nodo. Por lo tanto la profundidad de la raíz es siempre 0 y la de cualquier nodo es la de su padre más uno.
La altura de un nodo es la longitud del camino que va desde el nodo hasta la hoja más profunda bajo él. La altura de un árbol se define como la altura de su raíz.
Si hay un camino del nodo i al nodo v, entonces decimos que u es un ascendiente de v y que v es un descendiente de u.
El tamaño de un nodo es igual al número de descendientes que tiene (incluyendo dicho nodo). El tamaño de un árbol se define como el tamaño de su raíz.
Un árbol ordenado es aquel árbol con raíz en el que se ha especificado el orden de los hijos en cada nodo.

Propiedades

Dados dos nodos cualesquiera de un árbol, existe exactamente un camino que los conecta. Una consecuencia importante de esta propiedad es que cualquier nodo puede ser raíz, ya que, dado cualquier nodo de un árbol, existe exactamente un camino que lo conecta con cualquier otro nodo del árbol.
Un árbol con N nodos debe tener N − 1 aristas porque a cada nodo, excepto la raíz, le llega una arista.
La altura de cualquier nodo es uno más que la mayor altura de un hijo suyo.
Un árbol N-ario con n ≥ 0 nodos internos, contiene ( N − 1)n + 1 nodos externos.
Un árbol N-ario de altura h ≥ 0 tiene como máximo N^ h hojas.

Árbol binario

Un árbol binario es un árbol en el que ningún nodo puede tener más de dos hijos, se los distingue como izquierdo y derecho.

En general, la altura promedio de un árbol binario es O( N ) , pero puede llegar a ser N − 1 .

Árbol binario perfecto

Un árbol binario perfecto de altura h ≥ 0 es un árbol binario T = {r , TL , TR } con las siguientes propiedades:

Si h = 0 , entonces TL = vacío y TR = vacío
Por el contrario, si h > 0 , ambos TL y TR son árboles binarios perfectos de altura h − 1 .

Un árbol binario perfecto de altura h tiene exactamente 2^( h+1) − 1 nodos internos. Por lo tanto la cantidad de nodos permitido en este tipo de árboles es:

0, 1, 3, 7, 15, 31,..., (2^( h+1)) − 1,...

El peor caso para una búsqueda en un árbol binario perfecto es O(log n) .

Árbol binario completo

Un árbol binario en el que todos los niveles están llenos, excepto posiblemente el último nivel, el cual es completado de izquierda a derecha. Un árbol binario completo de altura

h ≥ 0 contiene al menos 2^h nodos y a lo sumo

(2^( h+1)) − 1 nodos.

Árbol binario balanceado

Un árbol binario está completamente balanceado si está vació, o ambos subárboles están completamente balanceados y tienen la misma altura. Por lo tanto, cualquier camino desde la raíz a una hoja tiene la misma longitud. Los únicos árboles que están perfectamente balanceados son los árboles binarios perfectos.

Un árbol binario no vacío T = {r , TL , TR } está AVL balanceado si H L − H R ≤ 1 , donde H L es la altura de TL y H R es la altura de TR . En otras palabras, en todos los nodos, la altura de la rama izquierda no difiere en más de una unidad de la altura de la rama derecha. Debido a esta propiedad estructural, el orden de complejidad de la búsqueda en estos árboles se mantiene en O(log n)

Recorrido de árboles

Esencialmente hay dos métodos distintos para visitar todos los nodos de un árbol, recorrido primero en profundidad y recorrido primero en anchura (u orden de nivel). Entre los de primero en profundidad se encuentran, preorden, postorden, en orden.

Preorden

El recorrido en preorden puede ser definido recursivamente de la siguiente manera:

Visitar primero la raíz.
Hacer un recorrido preorden a cada uno de los subárboles de la raíz, uno por uno en un orden determinado.

En el caso de de un árbol binario, el algoritmo resulta:

Visitar primero la raíz
Recorrer el subárbol izquierdo
Recorrer el subárbol derecho.

Inorden

El recorrido inorden, también llamado simétrico, solo puede ser usado en árboles binarios. En este recorrido, se visita la raíz entre medio de las visitas entre el subárbol izquierdo y el derecho.

Recorrer el subárbol izquierdo
Visitar la raíz
Recorrer el subárbol derecho.

Postorden

El último de los métodos de recorrido de árboles de primero en profundidad es el postorden. A diferencia del preorden donde se visita primero a la raíz, en el recorrido en postorden se visita la raíz a lo último.

Hacer un recorrido preorden a cada uno de los subárboles de la raíz, uno por uno en un orden determinado.
Visitar por último la raíz.

En el caso de los árboles binarios:

Recorrer el subárbol izquierdo
Recorrer el subárbol derecho.
Visitar por último la raíz.

Primero en anchura

En primero en anchura se visitan los nodos en el orden de su profundidad en el árbol. Primero se

visita todos los nodos en la profundidad cero (la raíz), y después todos los de profundidad igual a uno, etc. Para poder realizar una búsqueda de primera en anchura es necesario valerse de una estructura de datos auxiliar, la cola.

Poner en la cola la raíz.
Mientras que la cola no esté vacía
Quitar primero de la cola y asignarlo a una variable auxiliar, Nodo.
Imprimir el contenido de Nodo.
Si Nodo tiene hijo izquierdo, poner al hijo izquierdo en la cola.
Si Nodo tiene hijo derecho, poner al hijo derecho en la cola.

Representación implícita de árboles binarios

Representar un árbol binario mediante un array.

En este caso los nodos están almacenados en el array en vez de estar vinculados por medio de referencias. La posición del nodo en el array corresponde a su posición en el árbol. El nodo en la posición 0 es la raíz, el nodo en la posición 1 es el hijo izquierdo, y el nodo de la posición 2 es el hijo derecho. Se sigue con este procedimiento de izquierda a derecha en cada nivel del árbol. Los elementos que representan posiciones del árbol sin nodos son rellenados con 0 o con null.

Si el índice de un nodo es I entonces:

El hijo izquierdo del nodo es: 2 I + 1

El hijo derecho del nodo es: 2 I + 2

El padre de I es: ⎣(i − 1) / 2⎦

Los nodos sin llenar o nodos borrados dejan huecos en el array, desperdiciando memoria. Sin embargo, si el borrado de nodos no está permitido, puede ser una buena alternativa, y además es útil, si es muy costoso obtener memoria para cada nodo de forma dinámica.

Árboles de expresión

Tomamos como ej la expresión a / b + (c − d )e

Los nodos terminales (hojas) de un árbol de expresión son las variables o constantes en la expresión (a, b, c, d, y e). Los no terminales son los operadores (+,-× y ÷). Los paréntesis de la ecuación no aparecen en el árbol, ya que justamente las posiciones de los operadores en el árbol son los que le asignan prioridades. Para imprimir se usa el recorrido inorden y se utiliza el siguiente procedimiento:

Si se encuentra un nodo terminal, se lo imprime. De lo contrario, se hace lo siguiente:

Imprimir un paréntesis izquierdo
Recorrer el subárbol izquierdo
Imprimir la raíz
Recorrer el subárbol derecho.
Imprimir el paréntesis derecho.

Árboles de búsqueda

Soporta las operaciones de búsqueda, inserción y eliminación de forma eficiente. Las claves no aparecen en los nodos de forma arbitraria, sino que hay un criterio de orden que determina donde una determinada clave puede ubicarse en el árbol en relación con las otras claves en ese árbol.

Árbol binario de búsqueda

Una extensión del algoritmo de búsqueda binario que permite tanto inserciones como eliminaciones. El tiempo de ejecución de muchas de sus operaciones es de O(log N ) en el caso medio, pero en el peor de los casos puede llegar a O(N ) .

Puede definirse como un árbol que satisface la propiedad de búsqueda ordenada. Esto significa que para cada nodo X del árbol, los valores de todas las claves de su subárbol izquierdo son menores que la clave de X y los valores de todas las claves de su subárbol derecho son mayores que la clave de X .

Observaciones:

Si a este tipo de árbol se lo recorre en inorden se muestran los elementos ordenados de forma ascendente
no permite en principio la existencia de elementos duplicados, pero es posible modificarla para sí se permiten. Ante la existencia de dos claves duplicadas, una de las soluciones es tener una sola clave, y guardar un contador con el número de repeticiones.

Operaciones:

Búsqueda: Para buscar un elemento se empieza por la raíz y se desplaza repetidamente por las ramas izquierda o derecha, dependiendo del resultado de las comparaciones.
Búsqueda del minimo/maximo: el minimo se obtiene recorriendo repetidamente los nodos izquierdos hasta llegar a un nodo que no tenga hijo izquierdo. Para buscar el máximo se recorre de forma similar pero haciéndolo por la derecha.
La eliminación e inserción de nodos es una tarea que requiere de cierta complejidad. En el caso de querer eliminar un nodo se debe evitar que al hacerlo el árbol no quede desconectado.

El costo de las operaciones del árbol binario de búsqueda es proporcional al número de nodos consultados durante la operación. El costo de acceso a cada nodo es 1 más su profundidad.

Como conclusión, si el árbol está bien equilibrado, el costo de los accesos es logarítmico. árbol no equilibrado. Hay N nodos en el camino para recorrer hasta el nodo de mayor profundidad, con lo que el costo de la búsqueda en el peor de los casos es O(N ) . También es posible demostrar que en el caso medio, la mayoría de las operaciones requieren de un tiempo cercano a O(log N ).

Árboles M-arios

Un árbol N-ario es consiste de n subárboles T0 , T1 , K , Tn−1 y n − 1 claves K1 , K 2 K , K n−1 ,

T = {T0 , k1 , T1 , K 2 , T2 , K , K n−1 , Tn−1} donde 2 ≤ n ≤ M , de tal manera que las claves y nodos satisfacen las siguientes propiedades de ordenación de datos:

Las claves en cada nodo son distintas y están ordenadas, por ejemplo K i < K i +1 para 1 ≤ i ≤ n − 1
Todas las claves contenidas en el subárbol Ti −1 son menores que K i . Al árbol Ti −1 se lo llama subárbol izquierdo respecto de la clave K i .
Todas las claves contenidas en el subárbol Ti son mayores que K i . Al árbol Ti +1 se lo llama subárbol derecho respecto de la clave K i .

Árboles de búsqueda M-arios.

Si se tiene un conjunto de datos muy grande que no podemos colocar en la memoria principal, nos veríamos obligados a implementar el árbol de búsqueda en un almacenamiento secundario, como el disco. Las características de un disco a diferencia de la memoria principal hacen que sea necesario utilizar valores de M más grandes para poder implementar estos árboles de búsqueda de forma eficiente. Al elegir un valor de M grande, podemos arreglar para que un nodo de un árbol M-ario pueda ocupar un bloque de disco completo. Si cada nodo interno en el árbol M- ario tiene exactamente M hijos, puedes usar el siguiente teorema: h ≥ ⎡log base(M) (( M − 1)n + 1)⎤ − 1

Donde n es el número de nodos internos de un árbol de búsqueda. Un nodo en un árbol M-ario de búsqueda que tiene M hijos contiene exactamente M − 1 claves. Por lo tanto, en total hay

K = ( M − 1)n claves, entonces resulta h ≥ ⎡log base(M) ( K − 1) ⎤ − 1 .

Árboles-B

Los Árboles-B son Árboles BINarios balanceados diseñados para funcionar bien en discos magnéticos o en cualquier otro tipo de almacenamiento secundario de acceso directo. El objetivo principal es minimizar las operaciones de entrada y salida hacia el disco. Al imponer la condición de balance, el árbol es restringido de manera tal que se garantice que la búsqueda, la inserción y la eliminación sean todos de tiempo O(log N ) .

La cantidad de datos manejados puede ser tan grande que todos los datos no caben en memoria principal al mismo tiempo, entonces los algoritmos de árboles-B copian los bloques o páginas de disco a memoria principal a medida que se los necesita y se vuelve a escribir solo las páginas que han sido modificadas. Dado que estos algoritmos sólo necesitan una cantidad constante de páginas presentes en memoria principal a la vez, el tamaño de la memoria principal no limita el tamaño del árbol-B que puede ser manejado.

Definición

Un árbol-B de orden M es o bien un árbol vacío, o es un árbol M-ario de búsqueda T con las siguientes propiedades:

La raíz de T tiene al menos dos subárboles y a lo sumo M subárboles.
Todos los nodos internos de T (menos la raíz) tienen entre ⎡M / 2⎤ y M subárboles.
Todos los nodos externos de T están al mismo nivel.

Los nodos deben estar, al menos, medio llenos. Esto garantiza que el árbol no degenere en un simple árbol binario o ternario.

Arbol B+ : solo se almacenan los datos en las hojas del árbol (Ej NTFS, ReiserFS, XFS, índices de BDR)

Operaciones básicas sobre un árbol-B

Búsqueda:

Si necesitamos buscar un ítem x en un árbol-B, debemos comenzar por la raíz. Si el árbol está vacío, la búsqueda falla. De lo contrario, las claves en la nodo raíz son examinadas para determinar si el elemento que se está buscando está presente. Si está, la búsqueda termina exitosamente. Si no está, hay tres posibilidades a considerar:

Si el elemento x a buscar es menor que K1 , entonces se continúa buscando en el subárbol T0 .
Si x es más grande que K n−1 , se continúa buscando en el subárbol Tn−1 .
Si existe un i tal que 1 ≤ i ≤ n − 1 para el cual K i ≤ x ≤ K i+1 entonces se continúa buscando en el árbol Ti .

El tiempo de ejecución de una búsqueda exitosa depende por la profundidad en que se encuentre el elemento a buscar dentro del árbol. El tiempo de ejecución en el peor de los casos está determinado por la altura del árbol-B.

Inserción

Para insertar un elemento x , comenzamos en la raíz y realizamos una búsqueda para el. Asumiendo que el elemento no está previamente en el árbol, la búsqueda sin éxito terminará en un nodo hoja. Este es el punto en el árbol donde el x va a ser insertada.

Se pueden dar 2 situaciones:

Si el nodo hoja tiene menos de M − 1 claves en él, simplemente insertamos el elemento en el nodo hoja y damos por terminado.

Por cada clave que insertamos en el nodo, se requiere un nuevo subárbol. Si el nodo es una hoja, el subárbol a insertar está vacío. Por lo tanto cuando insertamos un elemento x, en verdad, estamos insertando el par de elementos ( x, φ ) .

La hoja está completa, es decir que queremos insertar el par ( x, φ ) , en un nodo T que ya tiene M − 1 claves. Esto resultaría en un nodo de árbol-B de orden M no válido por que tiene M + 1 subárboles y M claves. La solución es dividir el nodo T a la mitad (split), creando dos nodos, T 'L y T 'R , cada uno conteniendo la mitad de nodos que el original, y una clave restante, llamada k ⎡M / 2 ⎤ . Ahora hay dos casos para considerar:

Si T no es la raíz, se hace lo siguiente: Primero, T 'L reemplaza a T en el padre de T . Luego, tomamos el par (k ⎡M / 2 ⎤ , T 'R ) y lo insertamos recursivamente en el padre de T. Si el nodo padre se llena, entonces se divide también y los dos nuevos nodos son insertados en el abuelo. Este proceso continúa todo su camino hacia arriba del árbol hasta la raíz.
Cuando se llena la raíz también se divide. Sin embargo, dado que no hay padre al que insertar los dos nuevos hijos, una nueva raíz es insertada arriba de la vieja raíz. La nueva raíz va a contener exactamente dos subárboles y una sola clave.

Una cosa interesante para destacar, es que la altura del árbol-B solo se incrementa cuando el nodo raíz se divide. Lo que es más, cuando el nodo raíz se divide, las dos mitades son adjuntadas a la nueva raíz, por lo tanto todos los nodos externos permanecen a la misma profundidad, cumpliendo con la definición de árbol-B.

Eliminación

Hay dos estrategias populares de eliminación en un árbol B.

Buscar, eliminar el elemento y reestructurar el árbol para recuperar sus invariantes
Hacer una sola pasada por el árbol, pero antes de visitar un nodo, reestructurar el árbol para que una vez que se encontró la clave que desea eliminar, se pueda eliminar sin que se dispare la necesidad de una reestructuración más

Hay dos casos especiales a tener en cuenta cuando se elimina un elemento:

El elemento en un nodo interno es un separador para sus nodos hijos
Eliminación de un elemento puede poner su nodo con el número mínimo de elementos e hijos

Eliminación de un nodo de hoja

Busque el valor a eliminar.
Si el valor está en un nodo hoja, basta con eliminarlo del nodo.
Si ocurre desbordamiento, equilibrar el árbol

Eliminación de un nodo interno

Cada elemento de un nodo interno actúa como un valor de separación de dos sub-árboles, por lo tanto, tenemos que encontrar un reemplazo para la separación. Tenga en cuenta que el elemento más grande en el subárbol izquierdo es todavía menor que el separador. Del mismo modo, el elemento más pequeño en el subárbol derecho es todavía mayor que el separador. Ambos de estos elementos se encuentran en los nodos hoja, y, uno de los dos puede ser el nuevo separador de los dos subárboles. Descrito algorítmicamente a continuación:

Elegir un nuevo separador (ya sea el elemento más grande en el subárbol izquierdo o el elemento más pequeño en el subárbol derecho), retírese del nodo hoja que se encuentra, y vuelva a colocar el elemento a borrar con el nuevo separador.
El paso anterior elimina un elemento (el nuevo separador) de una hoja. Si ese nodo hoja es ahora deficiente (tiene menos que el número requerido de nodos), a continuación, equilibrar el árbol a partir del nodo de hoja.

Reequilibrio después de la eliminación

Comienza a partir de una hoja y procede hacia la raíz hasta que se equilibra el árbol. Si al eliminar un elemento de un nodo lo lleva debajo del mínimo permitido de elementos, entonces algunos elementos deben ser redistribuidos para que todos los nodos queden arriba del mínimo permitido. Por lo general, la redistribución implica mover un elemento a partir de un nodo hermano que tiene más que el número mínimo de nodos. Esa operación de redistribución se llama una rotación. Si ningún hermano puede prescindir de un nodo, el nodo deficiente debe ser combinado con un hermano. La fusión hace que el padre pierda un elemento de separación, por lo que el padre puede ser deficiente y la necesidad de reequilibrio. La fusión y el reequilibrio puede seguir todo el camino hasta la raíz. Dado que el número de elementos mínimo no se aplica a la raíz, haciendo la raíz es el único nodo deficiente no es un problema. El algoritmo para equilibrar el árbol es el siguiente:

Si existe hermano derecho del nodo deficiente y tiene más de un número mínimo de elementos, a continuación, rote a la izquierda

Copiar separador de los padres al final del nodo deficiente (el separador se mueve hacia abajo, el nodo deficiente ahora tiene el número mínimo de elementos)
Reemplazar separador de los padres con el primer elemento de la derecha hermano (hermano derecho pierde un nodo, pero todavía tiene al menos el número mínimo de elementos)
El árbol está equilibrado
De lo contrario, si existe hermano izquierdo del nodo deficiente y tiene más de un número mínimo de elementos, a continuación, rote a la derecha
Copiar separador de los padres para el inicio del nodo deficiente (el separador se mueve hacia abajo; nodo deficiente ahora tiene el número mínimo de elementos)
Reemplazar separador de los padres con el último elemento de la izquierda hermano (hermano izquierda pierde un nodo, pero todavía tiene al menos el número mínimo de elementos)
El árbol está equilibrado
De lo contrario, si ambos hermanos inmediatos tienen sólo el número mínimo de elementos, a continuación, combinar con un hermano
Copiar el separador hasta el final del nodo izquierdo (el nodo izquierdo puede ser el nodo deficiente o puede ser el hermano con el número mínimo de elementos)
Mueva todos los elementos del nodo derecho en el nodo izquierdo (el nodo izquierdo ya tiene el número máximo de elementos)
Ya no es necesario el nodo derecho y puede ser colocado en una lista libre
Retire el separador de los padres (el padre pierde un elemento)

Si el padre es la raíz y ahora no tiene elementos, entonces libere la vieja raíz y haga que el nodo combinado sea la nueva raíz (árbol se hace menos profunda)
De lo contrario, si el padre tiene menos que el número requerido de elementos, a continuación, equilibrar el padre

Nota: Las operaciones de reequilibrio son diferentes para los árboles B + (por ejemplo, la rotación es diferente porque los padres tiene copia de la clave) y B *-tree (por ejemplo, tres hermanos se fusionan en dos hermanos).

Arbol B+

Representa una colección de datos ordenados de manera que se permite una inserción y borrado eficientes de elementos. Es un índice, multinivel, dinámico, con un límite máximo y mínimo en el número de claves por nodo. Es una variación de un árbol B.

Toda la información se guarda en las hojas. Los nodos internos sólo contienen claves y punteros. Todas las hojas se encuentran en el mismo nivel, que corresponde al más bajo. Los nodos hoja se encuentran unidos entre sí como una lista enlazada para permitir búsqueda secuencial.

Características

El número máximo de claves en un registro es llamado el orden del árbol B +.
El mínimo número de claves por registro es la mitad del máximo número de claves. Por ejemplo, si el orden de un árbol B + es n, cada nodo (exceptuando la raíz) debe tener entre n/2 y n claves.
El número de claves que pueden ser indexadas usando un árbol B + está en función del orden del árbol y su altura.

Árbol B*

Es una variante de Árbol-B utilizado en los sistemas de ficheros HFS+ + y Reiser4, que requiere que los nodos no raíz estén por lo menos a 2/3 de ocupación en lugar de 1/2. Para mantener esto los nodos, en lugar de generar inmediatamente un nodo cuando se llenan, comparten sus claves con el nodo adyacente. Cuando ambos están llenos, entonces los dos nodos se transforman en tres. También requiere que la clave más a la izquierda no sea usada nunca.

No se debe confundir un árbol-B* con un árbol-B+, en el que los nodos hoja del árbol están conectados entre sí a través de una lista enlazada, aumentando el coste de inserción para mejorar la eficiencia en la búsqueda.

Métodos de Clasificación

Definamos formalmente el problema de la clasificación.

Entrada: Una secuencia de números {a1, a2, K , an} n ≥ 0

Salida: Una reclasificación {a '1, a '2, K , a ' n} de la secuencia inicial tal que a '1 ≤ a '2 ≤ K ≤ a ' n

Por ejemplo una secuencia de entrada como {31, 41, 59, 26, 41, 58} retorna la secuencia {26, 31, 41, 41, 58, 59}

La clasificación de los datos requiere al menos de dos operaciones fundamentales, la comparación de valores, es decir, el tipo de dato debe permitir determinar si un valor es menor, mayor o igual a otro y mover los valores a su posición ordenada, se debe poder reubicar los elementos.

Estabilidad

Un ordenamiento se considera estable si mantiene el orden relativo que tenían originalmente los elementos con claves iguales. Si se tiene dos registros A y B con la misma clave en la cual A aparece primero que B, entonces el método se considera estable cuando A aparece primero que B en el archivo ordenado.

La mayoría de los métodos de clasificación simples son estables, pero gran parte de los métodos complejos no lo son. Se puede transformar uno inestable en estable a costa de mayor espacio en memoria o mayor tiempo de ejecución.

Una de las ventajas de los métodos estables es que permiten que un array se ordene usando claves múltiples, por ejemplo, por orden alfabético del apellido, luego el nombre, luego el documento, etc.

In Situ

Los métodos in situ son los que transforman una estructura de datos usando una cantidad extra de memoria, siendo ésta pequeña y constante. Generalmente la entrada es sobrescrita por la salida a medida que se ejecuta el algoritmo. Por el contrario, los algoritmos que no son in situ requieren gran cantidad de memoria extra para transformar una entrada.

Fundamental para optimización debido a que utilizar la misma estructura disminuye los tiempos

de ejecución, ya que no se debe utilizar tiempo en crear nuevas estructuras, ni copiar elementos de un lugar a otro.

Clasificación interna y externa

Si el archivo a ordenar cabe en memoria principal, entonces el método de clasificación es llamado método interno, por otro lado si ordenamos archivos desde un disco u otro dispositivo, se llama método de clasificación externo. La diferencia radica en que el método interno puede acceder a los elementos fácilmente y de forma aleatoria, mientras que el externo debe acceder a los elementos de forma secuencial o al menos en grandes bloques de datos.

Teoría de la complejidad u orden de crecimiento de algoritmos

Estudia, de manera teórica, los recursos requeridos durante el cálculo para resolver un problema. Los recursos comúnmente estudiados son el tiempo (mediante una aproximación al número de pasos de ejecución de un algoritmo para resolver un problema) y el espacio (mediante una aproximación a la cantidad de memoria utilizada para resolver un problema). Difiere de la teoría de la computabilidad en que esta se ocupa de la factibilidad de expresar problemas como algoritmos efectivos sin tomar en cuenta los recursos necesarios para ello.

Los problemas que tienen una solución con orden de complejidad lineal son los problemas que se resuelven en un tiempo que se relaciona linealmente con su tamaño.

Hoy en día las máquinas resuelven problemas mediante algoritmos que tienen como máximo una complejidad o coste computacional polinómico, es decir, la relación entre el tamaño del problema y su tiempo de ejecución es polinómica. Éstos son problemas agrupados en el conjunto P. Los problemas con coste factorial o combinatorio están agrupados en NP. Estos problemas no tienen una solución práctica, es decir, una máquina no puede resolverlos en un tiempo razonable.

La complejidad en tiempo de un problema es el número de pasos que toma resolver una instancia de un problema, a partir del tamaño de la entrada utilizando el algoritmo más eficiente a disposición. Intuitivamente, si se toma una instancia con entrada de longitud n que puede resolverse en n^2 pasos, se dice que ese problema tiene una complejidad en tiempo de n^2. Por supuesto, el número exacto de pasos depende de la máquina en la que se implementa, del lenguaje utilizado y de otros factores. Para no tener que hablar del costo exacto de un cálculo se utiliza la notación O . Cuando un problema tiene costo en tiempo O(n^2 ) en una configuración de computador y lenguaje dado este costo será el mismo en todos los computadores, de manera que esta notación generaliza la noción de coste independientemente del equipo utilizado.

Clases de complejidad

Los problemas de decisión se clasifican en conjuntos de complejidad comparable llamados clases de complejidad.

La clase de complejidad P es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina determinista en tiempo polinómico, lo que corresponde intuitivamente a problemas que pueden ser resueltos aún en el peor de sus casos.

La clase de complejidad NP es el conjunto de los problemas de decisión que pueden ser resueltos por una máquina no determinista en tiempo polinómico. Todos los problemas de esta clase tienen la propiedad de que su solución puede ser verificada efectivamente.

Intratabilidad

Los problemas que pueden ser resueltos en teoría, pero no en práctica, se llaman intratables. Qué se puede y qué no en la práctica es un tema debatible, pero en general sólo los problemas que tienen soluciones de tiempos polinomiales son solubles para más que unos cuantos valores. Entre los problemas intratables se incluyen los de EXPTIME- completo. Si NP no es igual a P, entonces todos los problemas de NP-completo son también intratables.

Bubble sort

Uno de los más lentos y poco recomendables. Consiste en hacer N − 1 pasadas sobre los datos, donde en cada paso, los elementos adyacentes son comparados e intercambiados si es necesario. Durante la primera pasada el elemento más grande va “burbujeando” a la última posición del array. En general, luego de QUE pasadas por el array, los últimos K elementos del array se consideran bien ordenados por lo que no se los tendrá en cuenta.

El tiempo de ejecución en el peor de los casos es de O(n^2) y en el mejor es de O(n).

Selection Sort

Es más rápido que Bubble Sort, y no es mucho más complejo. Comienza buscando el elemento más pequeño del array y se lo intercambia con el que está en la primera posición, luego se busca el segundo elemento más pequeño y se lo coloca en la segunda posición. Se continua con este proceso hasta que todo el array está ordenado.

Insertion Sort

Es eficiente para ordenar arrays que tienen pocos elementos y están bien ordenados y, en la mayoría de los casos, es más rápido que Selection Sort y Bubble Sort. Se basa en la idea del ordenamiento parcial, en el cual hay un marcador que apunta a una posición donde a su izquierda se considera que están los elementos parcialmente ordenados.

El algoritmo comienza eligiendo el elemento marcado para poder insertarlo en su lugar apropiado en el grupo parcialmente ordenado, para eso sacamos temporalmente al elemento marcado y movemos los restantes elementos hacia la derecha. Nos detenemos cuando el elemento a ser cambiado es más pequeño que el elemento marcado, entonces ahí se intercambian el elemento que está en esa posición con la del elemento marcado. El tiempo de ejecución es de O(n^2) y es alcanzable si el array viene ordenado en orden inverso. Si el array está ordenado, el bucle interno no se ejecuta, tomando un tiempo O (n) .

Binary Insertion Sort: tiene en cuenta que la clasificación por inserción usa una búsqueda lineal para encontrar la posición del elemento marcado. Propone usar una búsqueda binaria dentro del grupo de elementos de la izquierda, el cual ya se encuentra ordenado. Con esta modificación requiere solo O (log n) comparaciones para hallar su posición.

Shell Sort

Primero compara los elementos que más lejanos y luego va comparando elementos más cercanos

para finalmente realizar un Insertion Sort. Para lograr esto se utiliza una secuencia H1 , H 2 , ... , H t denominada secuencia de incrementos. Cualquier secuencia es válida siempre que H1 = 1.

Después de ordenar usando la secuencia hk, se puede afirmar que todos los elementos separados por una distancia de hk estarán ordenados y por lo tanto se dice que está ordenado.

Una forma de implementar esto es aplicar Insertion Sort dentro de cada subvector hk independiente. Cuando el hk = 1 el método de ordenamiento es igual a un Insertion Sort. Esto se puede lograr modificándolo, para que incrementa o decrementa de a h unidades.

Uno puede visualizar el algoritmo Shell sort de la siguiente manera: coloque la lista en una tabla y ordene las columnas (usando un ordenamiento por inserción). Repita este proceso, cada vez con un número menor de columnas más largas. Al final, la tabla tiene sólo una columna. Mientras que transformar la lista en una tabla hace más fácil visualizarlo, el algoritmo propiamente hace su ordenamiento en contexto (incrementando el índice por el tamaño de paso, esto es usando i += tamaño de paso en vez de i + +).

Por ej, considere una lista de números como [13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10]. Si comenzamos con un tamaño de paso de 5, podríamos visualizar esto dividiendo la lista de números en una tabla con 5 columnas.

Cuando lo leemos de nuevo como una única lista de números, obtenemos

[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]. Aquí, el 10 que estaba en el extremo final, se ha movido hasta el extremo inicial. Esta lista es entonces de nuevo ordenada usando un ordenamiento con un espacio de 3 posiciones, y después un ordenamiento con un espacio de 1 posición (ordenamiento por inserción simple).

Una primera aproximación sugerida originalmente por Shell fue la de usar un incremento medio menor que el anterior (N/2). Si bien fue una mejora al Insertion Sort, esta secuencia no terminó siendo la mejor, ya que en algunos casos se terminaba teniendo un tiempo de ejecución de O(n^2) .

Otra aproximación, basada puramente en la experimentación, consiste en dividir cada intervalo por la constante 2,2 en vez de por 2, lo cual consigue un tiempo de ejecución promedio debajo de

O(n^(5 / 4)). Una de las secuencias que arroja mejores resultados es la secuencia de Knuth, se obtiene con la siguiente expresión recursiva: H = 3H + 1 . Cuando el valor inicial de H = 1

Primero se determina cual va a ser el h inicial. Se usa la fórmula H = 3H + 1 . El proceso termina cuando se encuentra un h más grande que el tamaño del array. De ahí en más se usa la inversa de la fórmula indicada anteriormente H = (h − 1) / 3 . Cada vez que iteramos el bucle exterior se disminuye el intervalo usando la fórmula inversa, y nos detenemos cuando el array fue 1-Bordado. La eficiencia se considera que este varía entre O(n^(3 / 2) ) y O(n^(7 / 6) ).

Merge Sort

Es un algoritmo recursivo que utiliza la técnica de divide y vencerás para obtener un tiempo de ejecución O (n log n) sin importar cual sea la entrada. Se basa en la fusión de dos o más secuencias ordenadas en una única secuencia ordenada. Una de las desventajas de este algoritmo es que requiere de memoria extra proporcional a la cantidad de elementos del array. Es un algoritmo a considerar si estamos buscando velocidad, estabilidad, donde no se tolera un ‘peor de los casos’ y además disponemos de memoria extra. Algo que hace más atractivo a Merge Sort es que suele acceder de forma secuencial a los elementos y es de gran utilidad para ordenar en ambientes donde

solo se dispone de acceso secuencial a los registros.

El algoritmo tiene como caso base una secuencia con exactamente un elemento en ella. Y ya que esa secuencia está ordenada, no hay nada que hacer. Por lo tanto para ordenar una secuencia n > 1 elementos se deben seguir los siguientes pasos:

Dividir la secuencia en dos subsecuencias más pequeñas.
Ordenar recursivamente las dos subsecuencias
Fusionar las subsecuencias ordenadas para obtener el resultado final.

Heap Sort

Se basa en una estructura de datos llamada montículo binario (ver apunte de árboles), que es una de las formas de implementar una cola de prioridad. Más precisamente un montículo binario es un árbol binario completo representado mediante un array, en el cual cada nodo satisface la condición de montículo. Para que se cumpla la condición de montículo la clave de cada nodo debe ser mayor (o igual) a las claves de sus hijos, si es que tiene. Esto implica que la clave más grande está en la raíz.

Este algoritmo tiene un tiempo de ejecución que nunca supera O (n log n) y no requiere espacio de memoria adicional (in situ).

Consiste de dos fases.

El array desordenado es transformado en un montículo desde abajo hacia arriba, es decir que empezamos desde las hojas y continuamos hacia la raíz. Cada nodo es la raíz de un sub montículo que cumple con la condición de montículo, excepto posiblemente en su raíz. Para eso intercambiamos la raíz con el hijo más grande, este proceso continúa hacia abajo, hasta que llegamos a una posición en donde la condición de montículo se cumple, o hasta que llegamos a una hoja. Este proceso de “filtrado descendente” comienza en ( N / 2) − 1 , ya que es esa la posición donde hay un nodo con al menos un hijo.
El vector ordenado se construye seleccionando el elemento más grande, quitándole del montículo y colocándolo en la secuencia ordenada. El elemento más grande del montículo se encuentra en la raíz, y siempre está en la posición 0 del array. Se intercambia repetidamente el elemento más grande del montículo por el próximo elemento de la posición en la secuencia ordenada. Después de cada intercambio, hay un nuevo valor en la raíz del montículo y el nuevo valor es filtrado hacia abajo hasta su posición correcta en el montículo, para que vuelva a cumplir con la condición de montículo.

Comparación con otros métodos

QuickSort suele ser un poco más rápido, debido a algunos factores, pero el peor de los casos el tiempo de quicksort ejecución es O (n^2), lo cual es inaceptable para grandes conjuntos de datos y puede ser provocada deliberadamente dado suficiente conocimiento de la aplicación, creando un riesgo de seguridad.

Por lo tanto, debido a que el límite superior en el tiempo de funcionamiento de heapsort es

O(n log n) y que su límite superior en almacenamiento auxiliar es constante, los sistemas integrados con restricciones de tiempo real o sistemas relacionados con la seguridad a menudo utilizan heapsort.

Heapsort también compite con Mergesort, que tiene los mismos límites de tiempo. Merge sort requiere Ω (n) espacio auxiliar, pero el heapsort requiere solamente una cantidad constante. Heapsort normalmente se ejecuta más rápido en la práctica en máquinas con pequeños o lentos cachés de datos . Por otro lado, Mergesort tiene varias ventajas sobre heapsort:

Merge sort sobre arays tiene mucho mejor rendimiento de la caché de datos, a menudo superando heapsort en las modernas computadoras de escritorio, ya que mergesort accede con frecuencia posiciones de memoria contiguas (buena localidad de referencia ), las referencias heapsort se extienden por todo el heap
Heapsort no es estable ; Merge sort es estable.
Merge sort paraleliza bien y puede alcanzar la linealidad con una implementación trivial; heapsort no es un candidato obvio para un algoritmo paralelo.
Merge sort se puede adaptar para funcionar con listas enlazadas con O (1) espacio adicional. Heapsort puede ser adaptado para operar en las listas doblemente enlazadas con sólo O (1) sobrecarga de espacio adicional.
Merge sort pertenece a la clasificación externa ; heapsort no lo es. La localidad de las referencias es el problema.

QuickSort

Es el algoritmo que mejor responde en la mayoría de los casos, con un tiempo promedio de O (n log n) y O(n^2 ) en el peor de los casos. Es recursivo pero se usan versiones iterativas para mejorar su rendimiento, también es in-situ, ya que usa solo una pila auxiliar. Está basado en la idea de divide y vencerás, en el cual un problema se soluciona dividiéndolo en dos o más subproblemas, resolviendo recursivamente cada uno de ellos para luego juntar sus soluciones para obtener la solución del original. Consiste en los siguientes cuatro pasos:

Si el número de elementos de S es 0 o 1, termina.
Elegir un elemento del conjunto ES, llamado pivote.
Particionar S en dos grupos, donde I = { x ∈ S − {v} | x ≤ v } y D = { x∈ S − {v} | x ≥ v }
Devolver el resultado de QuickSort(I), seguido de v y seguido del resultado de QuickSort(D)

Estrategia de partición

Una de las más usadas por ser in-situ y por su eficiencia es la siguiente. Se elige un pivote y se lo intercambia con el último elemento. Se tienen dos índices, izq que se mueve hacia la derecha y de que se mueve hacia la izquierda. El índice izq explora el array de derecha a izquierda y se detiene cuando encuentra un elemento mayor o igual al pivote. El índice de hace lo mismo en sentido contrario y se detiene al encontrar un elemento menor o igual al pivote. Los dos elementos en los que se detiene el proceso están mal ubicados y por lo tanto se los intercambia. Continuando de esta forma se tiene la seguridad que los elementos que están a la izquierda del índice izq son menores que el pivote y que los situados a la derecha de der son mayores.

Cuando los índices se encuentran el proceso se detiene, y se intercambia el último elemento con el elemento al que apunta el índice izq. Ahora el array está listo para llamar a QuickSort con los dos subconjuntos resultantes, es decir que se llamará a QuickSort(I) y a QuickSort(D).

Vale la pena observar que el algoritmo no necesita memoria auxiliar más allá de los índices, y que cada elemento es comparado con el pivote exactamente una vez.

Mejor de los casos

El mejor de los casos se obtiene cuando el proceso de particionamiento determina dos subsecuencias con cantidad de elementos iguales, es decir de N / 2 . Este caso produce un tiempo de ejecución cercano a O (n log n) .

Peor de los casos

El peor de los casos se da cuando el proceso de particionamiento produce una subsecuencia con N−1 elementos y otra con un solo elemento. Si esto ocurre en cada paso del algoritmo, dado que el particionamiento cuesta un tiempo EN , el tiempo de ejecución es de O(n^2) .

Seleccionando el pivote

Una mala elección sería elegir el primer elemento como pivote, que si bien sería aceptable en una entrada aleatoria nos llevaría al peor caso si la entrada está ya ordenada o en orden inverso.

Una mejor aproximación sería elegir el elemento central como pivote, es decir en la posición

(izq + der ) / 2 del array. Otra elección que es mucho mejor es la de elegir 3 valores, por ej el primero, el del medio y el último, y agarrar el menor de esos 3 como pivote.

Algoritmo de Huffman

Concepto

Define un código variable para cada carácter sin la necesidad de utilizar un prefijo. De esta manera es posible que, aquellos caracteres que son más frecuentes dentro de un alfabeto, se codifiquen con la menor cantidad de bits posibles mientras que aquellos que no sean tan frecuentes podrán tener una codificación un poco más amplia, pero siempre tendiendo a ser la menor posible.

Para ello, Huffman hace uso de una tabla de frecuencias donde se guardan los caracteres empleados en el texto y la cantidad de veces que son utilizados y de un árbol binario como estructura de datos. El código generado por el algoritmo, está basado en el código Morse y define una longitud variable de codificación basada en valores estadísticos.

El algoritmo se basa en :

Hallar los dos caracteres con la frecuencia más baja de la tabla de frecuencias. Si un carácter tiene frecuencia cero se ignora. Si dos o más caracteres tienen igual frecuencia se eligen dos cualesquiera.
Combinar los dos caracteres en un árbol binario. Cada hoja de este árbol contiene uno de los caracteres que se quiere codificar en el campo identificador, la frecuencia obtenida de la tabla de frecuencias en el campo frecuencia, nil en los campos hijo izq. e hijo der. y la dirección de la raíz del árbol en el campo padre. La raíz del árbol (o el padre de las hojas) contiene blancos o nulos en el campo identificador, la sumatoria de las frecuencias de sus hijos en el campo frecuencia y la dirección de cada hijo en los campos hijo de. e hijo izq. respectivamente.
Ejecutar nuevamente el punto 2). Esta vez entra en la comparación el valor de la frecuencia del árbol recientemente creado en lugar de las frecuencias de sus caracteres Este proceso se ejecuta hasta que quede sólo un árbol para todos los caracteres de la tabla de frecuencias y que de él pueda ser leído un char directamente.

Observaciones :

La optimización del algoritmo implica ocupar el menor espacio posible, por lo cual hay que tratar de disminuir la profundidad de los nodos maximales, es decir, la longitud de paso máximo.
El problema del prefijo, que se presenta en las codificaciones de longitud variable queda solucionado en el árbol de Huffman al ser el nodo máximo el que contiene el carácter. De esa manera, al detectar un nodo maximal, es decir Hijo De. = Hijo Izq. = nil puedo asegurar que en ese momento de la lectura de bits se produce el fin de la codificación de un carácter y que con el siguiente bit comenzará el próximo carácter.

Codificación y Decodificación

Una vez que se obtuvo la tabla de frecuencias y de esta, el árbol binario estamos en condiciones de decodificar un tren de bits. Por ej 000 010 111 10010

Por cada bit leído se deberá recorrer el árbol binario comenzando por la raíz y visitando los subárboles izquierdo o derecho según corresponda, de acuerdo a si el bit leído es un 0 ó un 1 respectivamente.

Para codificar un carácter, será necesario guardar la dirección que le fue asignada al nodo al haber sido dado de alta en el árbol. Una solución sería la de agregar otra columna en la tabla de frecuencias que contenga las direcciones físicas que ocupan los nodos que contienen los caracteres.

Obtenida la dirección del nodo que contiene el carácter que se quiere codificar, se recorre el árbol en forma ascendente mediante la dirección guardada en el campo que apunta al padre del nodo. Al bajar de nivel, en dirección a la raíz del árbol, se recupera un 0 ó un 1 en función de si el hijo es izquierdo (se codifica un 0) o si es derecho (un 1). Cada bit obtenido, es ingresado en una pila. Este proceso se ejecuta hasta llegar a la raíz del árbol (campo PADRE = nil). En este momento se tiene la codificación del carácter invertida en la pila por lo que al vaciar la pila, se obtendrá la codificación binaria del carácter.

Hashing

En las técnicas de búsqueda basadas en estructuras arbóreas, siempre es necesario comparar una cierta cantidad de claves hasta encontrar la buscada. Lo óptimo, sería minimizar la cantidad de comparaciones, evitando aquellas que se consideran innecesarias o redundantes con lo cuál se disminuirían los tiempos de recuperación. De esta manera es posible pensar en establecer una relación directa entre la dirección de los datos y el valor de la clave en lugar de obtener la dirección en función de la posición relativa de la clave respecto de las restantes.

Supongamos que el valor de la clave key es un número entero de tres dígitos. Puede definirse entonces una tabla, table(), de 999 elementos, donde cada uno guardará la dirección que le corresponda al valor absoluto de la clave tomado como subíndice.

Si bien este algoritmo es óptimo en términos de tiempos de recuperación, por no realizar ninguna comparación, es impracticable pues es imposible subordinar el valor de una clave a la cantidad máxima de elementos de una tabla.

Lo ideal sería hallar algún método que permita hallar la dirección de un registro en función de su clave, con la menor cantidad de comparaciones y ocupando el menor espacio posible.

Este método se denomina función de hashing, la cual identificamos con hash(), y puede definirse entonces como la función que aplicada a una clave devuelve el subíndice de la tabla (donde se encuentra la dirección con los datos del registro buscado).

Para minimizar el desperdicio, lo óptimo sería conocer previamente la cantidad máxima de registros que puede tener el archivo, maxrec, y dimensionar la tabla con un número máximo de elementos, maxtab, igual al primer número primo que sea mayor en valor absoluto a maxrec. Ejemplo 4 : si maxrec = 300 => maxtab = 307

El principal problema inherente a este método se produce cuando el valor que devuelve la función de hashing hash() es el mismo para dos o más claves iguales, lo que se define como colisión. Más precisamente:

Colisión : Sean k1 y k2 claves pertenecientes a los registros r1 y r2 respectivamente, con k1≠ k2. Y sea h(k) la función de hash. Si h(k1)=h(k2) entonces decimos que se produce una colisión.

La existencia de lo que llamamos colisiones es crucial debido a que, dado que la cantidad de claves posibles siempre es mayor que la cantidad de posiciones en la tabla, entonces siempre se producirán colisiones. Si bien pueden plantearse métodos que intenten reducir la probabilidad de colisión, la misma nunca llegará a ser cero. Lo que es un concepto en sí matemático, probabilístico (∀hash(key): P(colisión)>0), tiene una implicancia fundamental desde el punto de vista computacional, algorítmico: que inevitablemente se producirá una colisión al cabo de un tiempo finito.

Generalizando podríamos decir que: una función de hash es eficiente cuando minimiza el número de colisiones y ocupa los elementos de la tabla de manera uniforme. Si bien cuanto mayor sea el número de elementos de la tabla, menor será la probabilidad de colisión, el dimensionamiento desmesurado de la tabla ocasiona un desperdicio de espacio no deseado y otra vez se deberá analizar cada situación en particular, en términos de tiempo de procesamiento y espacio utilizado.

Funciones de hash

El principal objetivo de una función de hash es minimizar la probabilidad de colisión sin ocupar memoria innecesariamente. Existen distintos métodos pero en la práctica nunca se utiliza uno en particular sino una combinación de varios de acuerdo a la aplicación que se esté analizando.

Método de la división o del módulo

Consiste en obtener un valor entre 1 y maxtab resultante del resto de la división del valor numérico de la clave y maxtab, es decir que se utiliza la función módulo como función de hash. Ejemplo 6 : hash(key) = key mod 947 => hash(2866) = 25

Método del cuadrado medio.

Consiste en multiplicar el valor numérico de la clave por sí mismo y obtener un valor entre 1 y más de los dígitos medios del valor obtenido. Ejemplo 7 : si maxtab = 947 y se quiere hallar el valor de la clave 2866

hash(key) =números medios de ( key^2) =>

hash(2866) =8213956 => hash(2866) = 139

Si maxtab = 1013 podría tomarse indistintamente

hash(2866) = 2139 o hash(2866) = 1395

Método de dobles.

Consiste en dividir la cantidad de dígitos del valor numérico de la clave en dos o más partes iguales y realizar la operación por exclusiva con el valor binario de cada una de esas partes. Ejemplo 8 : si maxtab = 947 y se quiere hallar el valor de la clave 2866

Se divide la clave en dos partes: a1 = 28 y a2 = 66.

El valor binario de a1 es = 11100

El valor binario de a2 es = 1000010

La operación or exclusivo aplicada sobre los valores binarios de a1 y a2 dará un valor de subíndice en binario = 1011110 que pasado al sistema decimal es igual a : hash(2866) = 94

Clustering (relacionado a colisiones)

Cuando un elemento tiene una probabilidad de ser ocupado mucho mayor que otro.

Tratamiento de las colisiones

Hashing o direccionamiento abierto (Solución estática).

Se define hashing como la utilización de una segunda función de hash hasta que se encuentre una posición libre.

Varias soluciones:

Trivial: es la llamada solución lineal; si la posición de la tabla de direcciones, table(dir), en el valor de subíndice obtenido al aplicar la función de hash a una clave, dir, está ocupada, se ocupa la siguiente posición libre de la tabla. rhash(i) = (i+1) % maxtab El proceso consiste entonces en dada una clave key, se le aplica la función de hashing hash() y se obtiene un valor de subíndice dir, si el elemento de la tabla table(dir) está ocupado por otra clave, se aplicará una función de reasignación ra's() al valor dir para obtener un nuevo valor de subíndice. Este proceso es recursivo hasta hallar un elemento libre en la tabla.
Generalización de la solución lineal: rash(dir) = (dir + c) mod maxtab donde c y maxtab son números primos.
Doble hashing (para evitar el clustering): Este método utiliza en la función de reasignación otra función que toma como argumento el valor de la clave. Es decir : hash(key) = dir. Sí table(dir) es distinto de vacío, es decir está ocupada por otra clave,

rhash(dir) = (dir + f(key) mod(maxtab) donde f(key) es una función definida por el programador que toma como argumento el valor numérico de la clave.

Hacer depender la función de reasignación del número de veces que es aplicada. De esta manera, rash(dir, arg1) tendrá dos argumentos. rhash(dir, i) = (i+1) * dir mod maxtab donde i es una variable inicializada en 1

El principal problema del método de direccionamiento abierto, es que se basa en el uso de una estructura estática, es decir una tabla, la cuál debe ser dimensionada previamente y que en ocasiones puede resultar chica, en cuyo caso se deberá crear una tabla más grande y reorganizar todos los punteros en función del nuevo valor que tome maxtab. Otro problema es la dificultad que se presenta al dar de baja un elemento de la tabla. Este tipo de inconvenientes podría solucionarse con el uso de marcas de estado pero el proceso de recuperación sería cada vez más complejo y se perdería de vista los objetivos principales que se plantearon en un comienzo respecto de disminuir la cantidad de accesos y disminuir el espacio utilizado por las estructuras de datos auxiliares.

Observaciones:

Debe prestarse especial atención en el diseño del proceso de reasignación pues puede darse el caso de que un algoritmo busque eternamente un elemento disponible en la tabla o que informe que no hay más espacio disponible cuando en realidad sí hay elementos vacíos. Un ejemplo claro de una función de reasignación que pueda llegar a conclusiones equivocadas es la función

rhash(dir) = dir + 2. En este caso, llevado al extremo, puede darse que todos los elementos de la tabla con subíndice par estén ocupados, que los impares estén vacíos y la función indique que no existe más espacio disponible.

Chaining o encadenamiento. (soluciones dinámicas)

Consiste en enlazar entre sí los distintos pares de clave/puntero que colisionan entre sí, de forma tal de agruparlos. El encadenamiento puede darse en forma interna dentro de la misma tabla de hash, o también utilizando algún tipo de estructura auxiliar, lo que se conoce como “separate chaining”.

Hashing into buckets (separate chaining)

Permite resolver el problema de las colisiones a través de listas linkeadas que agrupan los registros cuyas claves randomizadas generan la misma dirección. Básicamente el proceso tiene como estructuras de datos una tabla principal, conocida como área base, y una lista linkeada, área de overflow, cuyo registro tiene tres campos. En uno se guarda la clave, en el otro se guarda la dirección en donde residen los datos y en el tercer campo se guarda la dirección del próximo registro con igual valor inicial de subíndice directo.

Procedimiento:

Cuando una función de hashing aplicada a una clave devuelve un elemento de tabla que fue ocupado previamente por otra clave, el proceso pide entonces una dirección de memoria para guardar los datos de la segunda clave y establece la relación mediante un link entre la primer clave, cuyos datos se encuentran en la tabla en el área base, con la segunda clave, situada en la lista linkeada en el área de overflow. Si se quisiera dar de baja el nodo, simplemente habría que dar una baja en la lista.

La principal desventaja de este procedimiento es que se utiliza espacio para los punteros, pero comparado con el método de direccionamiento abierto, es posible construir una tabla principal más pequeña con el consecuente ahorro de espacio y sin el problema que se presenta al tener todas las entradas de la tabla ocupadas. En este caso, deberá medirse la eficiencia del procedimiento a través de la cantidad de accesos que deberán realizarse, es decir la cantidad de nodos a recorrer en la lista, para hallar una clave dada. Si el número de nodos es muy grande, se perderá mucho tiempo en recuperar un dato, con lo cuál habría que rediseñar la función de hashing inicial o el tamaño de la tabla principal.

Hash Dinámico

Las tablas hash se presentaron como una alternativa hacia las estructuras tipo árbol ya que permitían el almacenamiento de grandes volúmenes de información y algoritmos eficientes para la administración sobre estas estructuras (inserción, eliminación y búsqueda).

Sin embargo, presenta 2 grandes problemas:

No existen funciones hash perfectas que permitan asegurar que por cada transformación de un elemento habrá una única correspondencia en la clave que contiene este elemento.
Son estructuras estáticas que no pueden crecer ya que necesitan un tamaño fijo para el funcionamiento de la estructura.

Para solucionar el segundo problema se implementa la utilización de métodos totales y métodos parciales. Convirtiendo la tabla hash en una estructura dinámica capaz de almacenar un flujo de información y no una cantidad fija de datos.

Métodos Totales

Método de las expansiones totales

El método de las expansiones totales consiste en realizar una duplicación del tamaño del arreglo establecido para realizar la tabla hash, esta expansión se ejecuta cuando se supera la densidad de ocupación . Así si se tiene una tabla hash de tamaño N, al realizar la expansión total se obtendrá una tabla hash de 2N, al realizar una segunda expansión se obtendrá una tabla hash de 4N, al realizar una tercera expansión se obtendrá una tabla hash de 8N y en general el tamaño de la tabla para una i-ésima expansión se define como aparece a continuación:

Dónde: N: Tamaño de la Tabla. i: Número de expansiones que se quieren realizar. T: Nuevo tamaño de la Tabla. La densidad de ocupación se define como el cociente entre el número de registros ocupados y el número de registros disponibles; así se tiene que: Dónde: ro: Registros Ocupados. rd: Registros Disponibles. ρo: Densidad de Ocupación. Cada vez que se pretende insertar un elemento es necesario calcular la densidad de ocupación, si se supera esta densidad se procede a implementar la expansión. Al realizar cada una de las expansiones es necesario volver a implementar la función hash para cada uno de los registros almacenados en la tabla y volver a insertarlos de nuevo en la tabla. Método de las reducciones totales Este método surge como una consecuencia del método de expansiones totales presentado anteriormente. En este método la densidad de ocupación disminuye de tal manera que acepta una reducción del tamaño de la tabla hash a la mitad. Así si se tiene una tabla hash de N, la primera reducción dará como resultado la N/2, la segunda reducción dará como resultado N/4, la tercera reducción dará N/8 y la i-ésima reducción dará como resultado: Dónde:N: Tamaño de la Tabla. i: Número de expansiones que se quieren realizar. T: Nuevo tamaño de la Tabla. Para realizar una reducción la densidad de ocupación se debe disminuir a un valor menor al rango establecido y los registros se deben eliminar de tal manera que los registros resultantes se puedan ingresar en una tabla hash que posea la mitad del tamaño de la tabla original. Cada vez que se implementó una reducción es necesario volver a utilizar la función hash con cada uno de los registros almacenados. Métodos Parciales Método de las expansiones parciales El método de las expansiones parciales consiste en incrementar en un 50% el tamaño del arreglo establecido para realizar la tabla hash, esta expansión se ejecuta cuando se supera la densidad de ocupación. Así si se tiene una tabla hash de tamaño N, al realizar la expansión parcial se obtendrá una tabla hash de 1.5 N, al realizar una segunda expansión se obtendrá una tabla hash de 2.25 N, al realizar una tercera expansión se obtendrá una tabla hash de 3.375 N y en general el tamaño de la tabla para una i-ésima expansión se define como: T = ↓( (1.5) ^ i * N ) Dónde:N: Tamaño de la Tabla. i: Número de expansiones que se quieren realizar. T: Nuevo tamaño de la Tabla. Cada vez que se pretende insertar un elemento es necesario calcular la densidad de ocupación, si se supera esta densidad se procede a implementar la expansión. Al realizar cada una de las expansiones es necesario volver a implementar la función hash para cada uno de los registros almacenados en la tabla hash y volver a insertarlos de nuevo en la tabla. Método de las reducciones parciales Este método surge como una consecuencia del método de expansiones parciales. En este método la densidad de ocupación disminuye de tal manera que acepta una reducción del tamaño de la tabla hash al 50%. Así si se tiene una tabla hash de N, la primera reducción dará como resultado la 0.5 N, la segunda reducción dará como resultado 0.25 N, la tercera reducción dará 0.125 N y la i-ésima reducción dará como resultado: T = ↑((0.5)^i*N) Dónde:N: Tamaño de la Tabla. i: Número de reducciones que se quieren realizar. T: Nuevo tamaño de la Tabla. Para realizar una reducción la densidad de ocupación debe disminuir a un valor menor al rango establecido y los registros se deben eliminar de tal manera que los registros resultantes se puedan ingresar en una tabla hash que posea la mitad del tamaño de la tabla original. Cada vez que se implementó una reducción es necesario volver a utilizar la función hash con cada uno de los registros almacenados.

B Tree VS Hash Table

B Tree

Supports equality and range searches, multiple attribute keys and partial key searches
Either a separate index or the basis for a storage structure
Responds to dynamic changes in the table

Hash Table

Does not support range search

Since adjacent elements in range might hash to different buckets, there is no way to scan buckets to locate all search key values v between v1 and v2
Although it supports multiple attribute keys, it does not support partial key search
Entire value of v must be provided to h
Dynamically growing files produce overflow chains, which negate the efficiency of the algorithm
The optimizer cannot use a hash index to speed up ORDER BY operations. (This type of index cannot be used to search for the next entry in order